package com.wuxuan.algorithm_homework.heap;

import java.util.Arrays;

/**
 * 堆
 * <p>
 * 基于数组实现一个大顶堆，并提供添加元素和删除堆顶元素的操作
 * 要求:
 * 插入操作(add()):时间复杂度为 0(logn)，其中n是队列中元素的数量。插入元素后，需要对堆进行调整.
 * 以维护堆的性质。
 * 删除操作(poll()):时间复杂度为 0(logn)。删除堆顶元素后，需要重新调整堆。
 * <p>
 * 要实现一个堆，我们首先要了解堆的概念。
 * 堆是一种完全二叉树，分为大顶堆和小顶堆，
 * ·大顶堆:每个节点的值都大于或等于其子节点的值，
 * 小顶堆:每个节点的值都小于或等于其子节点的值。
 * 完全二叉树:在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干节点。
 * <p>
 * 题：
 * 实现一个大顶堆，使用数组作为底层数据结构，并提供以下操作:
 * 添加元素(add):向堆中添加一个元素
 * 删除堆顶元素(poll):删除并返回堆顶元素(即最大值)
 */
public class MaxHeap {
    //存储堆中元素的数组
    private int[] heap;

    //堆中元素个数
    private int size;

    //堆的初始容量，如果超出容量，则两倍扩容
    private int capacity;

    public MaxHeap(int capacity) {
        this.capacity = capacity;
        heap = new int[capacity];
        size = 0;
    }

    /**
     * 添加元素
     *
     * @param value
     */
    public void add(int value) {
        if (size == capacity) {
            capacity *= 2;
            //要加元素的话要扩容了！
            Arrays.copyOf(heap, heap.length * 2);
        }
        //添加在最后面
        heap[size++] = value;
        //进行上浮操作
        heapifyUp();
    }

    /**
     * 进行上浮操作
     */
    private void heapifyUp() {
        int index = size - 1;
        int parentIndex = (index - 1) / 2;

        while (index >= 0 && heap[index] > heap[parentIndex]) {
            swap(heap, index, parentIndex);
            index = parentIndex;
            parentIndex = (index - 1) / 2;
        }
    }

    private void swap(int[] heap, int index1, int index2) {
        int temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }

    /**
     * 删除并返回堆顶元素
     */
    public int poll() {
        //思：要删除堆顶的，那么整个数组把最后一个先替上来，堆顶换到最后。维持堆的样子，然后再把替上来的元素下沉，维持堆的性质。
        // 最后把最后一个元素即原来的堆顶删掉即可,?,或者说直接size--，由于原堆顶在最后一个位置，相当于并不存在了
        if (size == 0) {
            return Integer.MIN_VALUE;
        }

        int maxValue = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown();

        return maxValue;
    }

    /**
     * 下沉操作，维持堆的性质
     */
    private void heapifyDown() {
        int index = 0;
        int leftChildIndex = index * 2 + 1;
        int rightChildIndex = index * 2 + 2;
        while (leftChildIndex < size) {
            int largerChildIndex = leftChildIndex;
            if (rightChildIndex < size && heap[rightChildIndex] > heap[largerChildIndex]) {
                largerChildIndex = rightChildIndex;
            }

            if (heap[index] >= heap[largerChildIndex]) {
                break;
            }

            swap(heap, index, largerChildIndex);
            //准备下一次
            index = largerChildIndex;
            leftChildIndex = index * 2 + 1;
            rightChildIndex = index * 2 + 2;
        }
    }

}
